#include "stdafx.h"
#include "stdlib.h"
#include "time.h"

struct Elem
{
	Elem* next;
	Elem* prev;
	int value;
};
struct DList
{
	Elem* head;
	Elem* tail;
	int size;
};
DList* createDList()
{
	DList* dl=(DList*)malloc(sizeof(DList));
	dl->head=NULL;
	dl->tail=NULL;
	dl->size=0;
	return dl;
}
Elem* createElem(int value)
{
	Elem* el=(Elem*)malloc(sizeof(Elem));
	el->next=NULL;
	el->prev=NULL;
	el->value=value;
	return el;
}
void append_to_begin(DList* list, Elem* elem)
{
	if(list->tail==NULL)
		list->tail=elem;
	elem->next=list->head;
	//elem->prev=NULL;
	list->head=elem;
	if(elem->next!=NULL)
		elem->next->prev=elem;
	if(elem->prev!=NULL)
		elem->prev->next=elem;
	list->size++;
}
void append_to_end(DList* list, Elem* elem)
{	
	if(list->head==NULL)
		list->head=elem;
	elem->prev=list->tail;
	list->tail=elem;
	if(elem->prev!=NULL)
		elem->prev->next=elem;
	if(elem->next!=NULL)
		elem->next->prev=elem;
	list->size++;
}
struct Elem* findElem(DList* list,int pos)
{
	Elem* elem=list->head;
	for(int i=2;i<=pos;i++)
		elem=elem->next;
	return elem;
}
void print_list(DList* list)
{
	Elem* el = list->head;
	for(int i=1;i<(list->size);i++)
	{
		printf("%d ",el->value);
		el=el->next;
	}
	printf("%d\n",el->value);
}
int find_pos(DList* list, Elem* el)
{
	Elem* curr=list->head;
	for(int i=1;i<=list->size;i++)
	{if(el==curr)
	return i;
	if(curr->next!=NULL)
	curr=curr->next;}
}
void swap(DList* list,Elem* a,Elem* b)
{
	Elem* temp;
	if(find_pos(list,a)>find_pos(list,b))
	{temp=a;a=b;b=temp;}
	Elem* preva=a->prev;
	Elem* posta=a->next;
	Elem* prevb=b->prev;
	Elem* postb=b->next;

	if(posta==b)
	{
		if(preva==NULL)
			list->head=b;
		else
			preva->next=b;
		if(postb==NULL)
			list->tail=a;
		else
			postb->prev=a;
		
		b->prev=preva;
		b->next=a;
		a->prev=b;
		a->next=postb;
	}
	else
		{	if(preva==NULL)
				list->head=b;
			else
				preva->next=b;
			if(postb==NULL)
				list->tail=a;
			else
				postb->prev=a;
			
			b->prev=preva;
			b->next=posta;
			posta->prev=b;
			prevb->next=a;
			a->prev=prevb;
			a->next=postb;
		}
}
void sorting(DList* list)
{
	Elem* curr=list->head;
	Elem* place=list->head;
	Elem* min=list->head;
	for(int j=1;j<=(list->size-2);j++)
	{
		for(int i=j;i<=(list->size);i++)
		{
			if((curr->value)<(min->value))
				min=curr;
			if(curr!=NULL)
			curr=curr->next;
		}
		swap(list,place,min);
		if(place!=NULL)
		place=min->next;
		curr=min->next;
		min=min->next;
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	struct DList* klen=createDList();
	srand(time(NULL));
	for(int i=1;i<=10;i++)
	{
		struct Elem* cherv=createElem(rand()%100);
		//struct Elem* cherv2=createElem(i);
		//append_to_begin(klen, cherv2);
		append_to_end(klen, cherv);
	}
	print_list(klen);
	Elem* a=findElem(klen,1);
	Elem* b=findElem(klen,6);
	sorting(klen);
	//swap(klen,a,b);
	//swap(klen,b,a);
	print_list(klen);
	return 0;
}